﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using snat.model;
using QuickGraph;
using snat.algorithms;
using algorithms.algorithms.utils.datastructures;
using System.IO;



namespace algorithms.algorithms.PageRankAlgorithm {
    /// <summary>
    /// Implements the PageRank ranking algorithm. This algorithm, which forms the basis of the Google search engine,
    /// has proven applicable to use within social networking.
    /// It was first described in the paper "The PageRank Citation Ranking: Bringing Order to the Web",
    /// available online at http://ilpubs.stanford.edu:8090/422/ (Accessed on 01/05/2011)
    /// </summary>
    public class PageRank : IAlgorithm, ITextRenderable, IReaderWriter {
        public event RenderTextDelegate RenderText;

        /// <summary>
        /// A dictionary of the integer node id to a double scoring value. 
        /// Provided for completeness, however the Ranking is the main output of this algorithm
        /// </summary>
        public Dictionary<int, double> Scoring {
            get;
            private set;
        }

        /// <summary>
        /// Returns A list of nodes ordered by score - the ranking.
        /// </summary>
        public List<BaseNode> Ranking {
            get {
                List<KeyValuePair<int, double>> ordering = Scoring.OrderByDescending(e => e.Value).ToList();
                return ordering.ConvertAll(kvp => NetworkModel.Instance.Nodes[kvp.Key]);
            }

        }

        public readonly double d;
        public readonly int Rounds;

        public PageRank(double _d = 0.85, int _rounds = 1000) {
            d = _d;
            Rounds = _rounds;
        }

        /// <summary>
        /// PageRank suffers from the 'Dangling Link' problem. It is not clear where to re-distribute rank from with no out-degree.
        /// To combat this
        /// </summary>
        /// <returns>An adjacency list representing the trimmed network structure</returns>
        private AdjacencyList<int> GenerateOverlay() {
            //Generate pagerank overl
            AdjacencyList<int> connectedNetwork = new AdjacencyList<int>();
            foreach (BaseNode b in NetworkModel.Instance.Nodes.Values) {
                foreach (var e in b.OverlayOutEdges) {
                    connectedNetwork.TryAddLink(b.ID, e.Target.ID);
                }
            }
            return connectedNetwork;
        }


        private AdjacencyList<int> Trim(AdjacencyList<int> fullnetwork) {
            AdjacencyList<int> network = fullnetwork.Clone() as AdjacencyList<int>;
            int removed, total = 0;
            do {
                removed = 0;
                foreach (int node in network.Entities.ToList()) {
                    if (network.OutEdgesOf(node).Count == 0) { //remove rank sinks
                        network.Delete(node);
                        removed++;
                    }
                }
                total += removed;
                Console.WriteLine("Removed {0} chaps, now a total of {1}. There are {2} chaps remaining", removed, total, network.Entities.Count);
            }
            while (removed > 0);
            return network;
        }


        public void DoRanking() {
            AdjacencyList<int> fullNetwork = GenerateOverlay();
            AdjacencyList<int> connectedNetwork = Trim(fullNetwork);
            double popSize = connectedNetwork.Entities.Count;
            Dictionary<int, double> newScoring = fullNetwork.Entities.ToDictionary(e => e, e => connectedNetwork.Entities.Contains(e) ?
            1.0 / popSize : 0.0);

            for (int i = 0; i < Rounds; i++) {
                newScoring = PageRankIteration(newScoring, connectedNetwork);
            }

            //one last iteration to ensure everyone (including dangling) is ranked
            Scoring = PageRankIteration(newScoring, fullNetwork);
            if (RenderText != null) RenderText(this);
        }

        /// <summary>
        /// Performs one iteration of the PageRank algorithm
        /// </summary>
        /// <param name="scores">scores prime, the result of the last iteration </param>
        /// <param name="network"> The network representation - trimmed for all but the last iteration</param>
        /// <returns></returns>
        private Dictionary<int, double> PageRankIteration(Dictionary<int, double> scores, AdjacencyList<int> network) {
            Dictionary<int, double> scoresPrime = network.Entities.ToDictionary(e => e, e => 0.0);
            double popSize = network.Entities.Count;
            foreach (int k in network.Entities) {
                if (!scoresPrime.ContainsKey(k)) scoresPrime.Add(k, 0.0);
                scoresPrime[k] = ((1.0 - d) / popSize + d * network.InEdgesOf(k).Sum(e => scores.ContainsKey(e) ? scores[e] / (double)network.OutEdgesOf(e).Count : 0));
            }
            return scoresPrime;
        }


        public string Name {
            get { return "PageRank"; }
        }



        public void Register() {
            NetworkModel.Instance.TapeEnded += DoRanking;
            NetworkModel.Instance.TapePaused += DoRanking;
        }

        public void DeRegister() {
            NetworkModel.Instance.TapeEnded -= DoRanking;
            NetworkModel.Instance.TapePaused -= DoRanking;
        }


        #region ITextRenderable Members


        public string GetRenderableText() {
            StringBuilder ret = new StringBuilder();
            foreach (KeyValuePair<int, double> kvp in Scoring.OrderByDescending(e => e.Value)) {
                ret.Append(NetworkModel.Instance.Nodes[kvp.Key].Name);
                ret.Append(" : ");
                ret.AppendLine(kvp.Value.ToString());
            }
            return ret.ToString();
        }

        #endregion

        #region IReaderWriter Members

        public void Write(string filePath) {
            using (StreamWriter output = new StreamWriter(filePath)) {
                output.WriteLine("name, id, value");
                foreach (KeyValuePair<int, double> v in Scoring.OrderByDescending(kvp => kvp.Value)) {
                    output.WriteLine("{0}, {1}, {2}\n", NetworkModel.Instance.Nodes[v.Key].Name, v.Key, v.Value);
                }
            }
        }

        public string Read(string filePath) {
            StringBuilder ret = new StringBuilder();
            using (StreamReader input = new StreamReader(filePath)) {
                while (!input.EndOfStream) {
                    ret.Append(input.ReadLine());
                }
            }
            return ret.ToString();
        }

        #endregion
    }
}
